package com.sourcetrip.my.inter.functional;


import com.sourcetrip.my.modle.TreeNode;

/**
 * @author: ZhouBert
 * @date: 2020/12/18
 * @description: 自平衡树的接口 提供用于自平衡的接口
 * 由于 AVL-Tree 和 RedBlackTree 都有旋转至平衡的特性，于是抽象为接口
 * PS:由于 AVL-Tree 已经实现在前，所以本接口不再接入 AVLTreeV0,而是接入 RedBlackTree
 */
public interface SelfBalancedTree<E> {

	/**
	 * 将 grand 左旋
	 * 保证 grand,parent != null
	 * child may null
	 *
	 * @param grand
	 */
	default void rotateLeft(TreeNode<E> grand) {
		TreeNode<E> parent = grand.right;
		TreeNode<E> child = parent.left;

		grand.right = child;
		parent.left = grand;
		rotateCommon(grand, parent, child);
	}

	/**
	 * 将 grand 右旋
	 *
	 * @param grand
	 */
	default void rotateRight(TreeNode<E> grand) {
		TreeNode<E> parent = grand.left;
		TreeNode<E> child = parent.right;

		grand.left = child;
		parent.right = grand;
		rotateCommon(grand, parent, child);
	}


	default void rotateCommon(TreeNode<E> grand, TreeNode<E> parent, TreeNode<E> child) {
		TreeNode<E> prev = grand.parent;
		if (prev != null) {
			if (grand.isLeftChild()) {
				prev.left = parent;
			} else {
				prev.right = parent;
			}
		}
		parent.parent = prev;
		grand.parent = parent;
		if (child!=null){
			child.parent = grand;
		}

		afterRotate(prev, grand, parent, child);
	}

	/**
	 * 钩子方法：用于旋转之后的处理
	 *
	 * @param prev grand 的前节点
	 * @param grand
	 * @param parent
	 * @param child
	 */
	void afterRotate(TreeNode<E> prev, TreeNode<E> grand, TreeNode<E> parent, TreeNode<E> child);

}
